package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 2267. 检查是否有合法括号字符串路径
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/23 13:11
 */
public class HasValidPath {

    public static void main(String[] args) {
        HasValidPath test = new HasValidPath();

        // true
//        char[][] grid = {{'(', '(', '('}, {')', '(', ')'}, {'(', '(', ')'}, {'(', '(', ')'}};

        // false
//        char[][] grid  = {{')',')'},{'(','('}};

        // false
        char[][] grid  = {{'(',')','(','(',')','(','(','(','(','(',')','(',')',')','(','(',')',')','(','(',')','(','(','(',')','(',')',')',')','(',')','(',')','(',')'},{')','(',')','(',')','(',')',')',')',')','(',')','(','(',')',')','(','(','(','(',')',')','(',')','(','(','(','(',')',')','(','(',')','(','('},{')','(',')','(','(',')',')',')',')',')','(',')',')',')',')','(',')','(',')','(',')','(','(','(',')',')','(',')','(',')',')',')','(','(',')'},{')',')',')','(','(',')','(',')','(','(','(','(',')',')',')','(','(',')',')',')',')','(',')',')','(',')','(',')','(','(','(','(','(','(',')'},{')','(',')','(',')',')',')',')','(',')','(',')','(',')','(',')','(','(',')','(',')','(','(','(','(','(',')',')',')',')',')','(',')',')','('},{')',')','(',')',')','(','(',')','(','(','(',')','(','(','(',')','(','(','(',')','(','(',')',')','(','(','(','(',')',')','(',')',')','(',')'},{')',')',')',')',')','(','(',')',')',')','(','(',')',')','(','(',')','(',')',')',')','(',')','(',')','(','(',')','(','(',')','(',')',')',')'},{'(',')',')',')','(','(',')','(','(',')',')','(',')','(','(','(','(',')','(','(','(','(',')',')',')','(',')',')','(','(','(','(','(','(',')'},{'(',')',')','(',')',')',')','(','(',')','(','(','(',')','(','(',')',')',')',')','(',')','(',')',')','(','(','(',')','(','(','(','(','(','('},{'(',')',')',')','(','(','(',')','(','(','(','(','(','(',')','(',')',')','(','(','(',')','(','(',')','(',')','(',')','(',')',')','(',')',')'},{')','(','(',')','(','(',')',')',')','(',')',')',')',')','(','(','(','(',')',')','(','(','(','(',')','(','(',')',')','(','(',')',')','(','('},{')','(','(',')','(','(','(',')',')','(','(',')',')',')','(','(',')',')','(','(',')','(',')',')','(','(',')','(',')',')','(','(',')',')',')'},{')',')',')',')',')',')','(',')',')',')','(','(','(','(',')',')',')','(',')',')',')',')',')','(','(',')','(','(',')','(','(','(',')',')',')'},{'(',')',')','(',')',')',')','(','(',')',')','(',')','(','(','(',')',')',')','(','(',')',')','(','(',')','(',')',')',')','(',')','(','(','('},{')',')','(',')',')','(','(','(',')','(','(','(','(','(',')','(','(',')',')','(','(','(',')',')',')',')','(','(','(',')','(',')',')','(','('},{'(','(',')','(',')',')','(',')',')','(','(',')','(',')',')','(',')',')',')',')','(','(',')','(','(','(',')',')',')',')','(','(','(',')',')'}};

        System.out.println(grid.length);
        System.out.println(grid[0].length);
        boolean b = test.hasValidPath(grid);
        System.out.println(b);

    }

    public boolean hasValidPath(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int size = ((m + n - 1) >> 1) + 1;
        int[][][] arr = new int[m][n][size];
        if (grid[0][0] == ')' || grid[m - 1][n - 1] == '(') {
            return false;
        }
        arr[0][0][1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int[] items = arr[i][j];
                if (grid[i][j] == '(') {
                    if (i > 0) {
                        int[] ints = arr[i - 1][j];
                        for (int k = size - 2; k >= 0; k--) {
                            items[k + 1] |= ints[k];
                        }
                    }
                    if (j > 0) {
                        int[] ints = arr[i][j - 1];
                        for (int k = size - 2; k >= 0; k--) {
                            items[k + 1] |= ints[k];
                        }
                    }
                } else {
                    if (i > 0) {
                        int[] ints = arr[i - 1][j];
                        for (int k = size - 1; k > 0; k--) {
                            items[k - 1] |= ints[k];
                        }
                    }
                    if (j > 0) {
                        int[] ints = arr[i][j - 1];
                        for (int k = size - 1; k > 0; k--) {
                            items[k - 1] |= ints[k];
                        }
                    }
                }
            }
        }
        return arr[m - 1][n - 1][0] > 0;
    }

}
